Images displayed by computer graphics are comprised of many small polygons of various shapes and sizes. Algorithms used to create a polygon using digital techniques are well known. However, they are generally implemented in software on a microprocessor. For real time applications, that is, situations where the display must be updated 20 times a second or more, the current state of the art is too slow. This is due to the fact that prior art devices depend primarily on software techniques and do not incorporate a viable hardware approach.
The present invention overcomes the disadvantages of the prior art by implementing a polygon tiling algorithm in electronic hardware, thereby allowing a much faster polygon tiling speed. The invention also provides a means to pipeline the polygon data so that a new polygon can be loaded into the hardware at the same time it is being tiled, and simultaneously as a tiled polygon is being provided as output information to a graphics rendering engine.
One method of generating three dimensional graphics initially generates three dimensional polygons which form the graphics. The process of generating such polygons is referred to as tiling. Tiling can occur in one of two places during the polygon rendering process in a graphic display system. In a first case, a set of points can be tiled and then transformed from world space into screen space. This approach has disadvantages in that a point may undergo transformation multiple times. Such an approach degrades the performance of the transformation unit, or may require a higher throughput from the transformation unit in order to meet system requirements. In a second approach, the points are tiled after transformation. This eliminates the disadvantage caused by the first method. When terrain is being transformed, as in the case of a digital map application, it is desirable to transform a string of data posts as one object in order to take advantage of algorithmic simplification and the transformation. In order to generate the polygons, two lines of objects of transformed points are required. It is desirable to use the polygon tiling engine in a system for more than just tiling terrain. Therefore, it must have the flexibility to handle objects of any kind, in order to keep the cost of the total system to a minimum. In a digital map system the polygon tiling engine is needed in order to generate three dimensional objects like terrain features or symbology.